|
Chinese Whispers is a clustering method used in network science named after the famous whispering game.〔Chris Biemann,("Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems" ), 2006〕 Clustering methods are basically used to identify communities of nodes or links in a given network. This algorithm was designed by Chris Biemann and Sven Teresinak in 2005.〔 The name comes from the fact that the process can be modeled as a separation of communities where the nodes send the same type of information to each other.〔 Chinese Whispers is a hard partitioning, randomized, flat clustering (no hierarchical relations between clusters) method.〔 The random property means that running the process on the same network several times can lead to different results, while because of hard partitioning one node can only belong to one cluster at a given moment. The original algorithm is applicable to undirected, weighted and unweighted graphs. Chinese Whispers is time linear which means that it is extremely fast even if the number of nodes and links are very high in the network.〔 ==Algorithm== The algorithm works in the following way in an undirected unweighted graph:〔 # All nodes are assigned to a random class. The number of initial classes equals the number of nodes. # Then all of the network nodes are selected one by one in a random order. Every node moves to the class which the given node connects with the most links. In the case of equality the cluster is randomly chosen from the equally linked classes. # Step two repeats itself until a predetermined number of iteration or until the process converges. In the end the emerging classes represent the clusters of the network. The predetermined threshold for the number of the iterations is needed because it is possible, that process does not converge. On the other hand in a network with approximately 10000 nodes the clusters does not change significantly after 40-50 iterations even if there is no convergence.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chinese Whispers (clustering method)」の詳細全文を読む スポンサード リンク
|